package ali;

/**
 * 动态规划分析思路：
 *
 * 对于一个子串而言，如果它是回文串，并且长度大于 22，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串 \textrm{``ababa''}“ababa”，如果我们已经知道 \textrm{``bab''}“bab” 是回文串，那么 \textrm{``ababa''}“ababa” 一定是回文串，这是因为它的首尾两个字母都是 \textrm{``a''}“a”
 *
 * 作者：LeetCode-Solution
 * 链接：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author wxh
 */
public class Solution_20 {

	public String longestPalindrome(String s) {

		int n = s.length();
		boolean[][] dp = new boolean[n][n];
		String ans = "";
		for (int l = 0; l < n; ++l) {
			for (int i = 0; i + l < n; ++i) {
				int j = i + l;
				if (l == 0) { //对于长度为1的子串，它显然是个回文串
					dp[i][j] = true;
				} else if (l == 1) { //对于长度为2的子串，只要它的两个字母相同，它就是一个回文串
					dp[i][j] = (s.charAt(i) == s.charAt(j));
				} else { //子串长度大于 2
					dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]); //只有 s[i+1,j-1] 是回文串，并且 s 的第i和j个字母相同时，s[i,j]才会是回文串
				}

				if (dp[i][j] && l + 1 > ans.length()) {
					ans = s.substring(i, i + l + 1);
				}

			}
		}
		return ans;
	}

}